package java学习.代码随想录.动态规划;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/9 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 不同的二叉搜索树 {

    public static int numTrees(int n) {
    /**
     * 1.dp数组含义： i个节点的二叉搜索树的数量
     * 2.
     *   以3为例：
     *   dp[3] = 以1开头的二叉搜索树 + 以2开头 +以3开头
     *   以1开头的二叉搜索树 = 左子树有0搜素二叉树的数量 * 右子树有2元素的搜素二叉树的数量 = dp[0] * dp[2]
     *   以2开头 = 左子树有1个元素的二叉搜索树数量 * 右子树有一个元素的二叉搜索树的数量   = dp[1] * dp[1]
     *   以3开头 = 左子树有2元素搜素二叉树的数量 * 右子树有0元素的搜素二叉树的数量       = dp[2] * dp[0]
     *   则 dp[3] = dp[0] * dp[2] + dp[1] * dp[1]  +    dp[2] * dp[0]
     *   即： dp[i] += dp[j-1] * dp[i-j]  ( i和j 都从1开始 )
     * 3. 初始化：
     *  dp[0] = dp[1] = 1;  因为 0个节点 也算1个二叉搜索树。
     *  dp[2] = 2;
     * 4. 都从1开始遍历
     */
        int[] dp = new int[n+1];
        dp[0] =  1;
        dp[1] = 1;
//        dp[2] = 2;
        for (int i = 2 ; i <=n; i++) {
            for (int j = 1; j <=i; j++) {
                dp[i] +=dp[j-1]*dp[i-j];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }
    public static int numTrees1(int n) {
        //初始化 dp 数组
        int[] dp = new int[n + 1];
        //初始化0个节点和1个节点的情况
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
                //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }
    public static void main(String[] args) {

        System.out.println(numTrees(5));
        System.out.println(numTrees1(5));
    }
}
